package gold.digger;

import gold.utils.InputUtil;

import java.util.*;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC1488 {
    public long startExecuteTime = System.currentTimeMillis();

    /*
     * @param 此题目参考了别人代码
     * 这是因为问题情况较为复杂
     * 未来需要再次复习此道题目
     * hash的题目真的是恶心啊
     * @return:
     */
    class Solution {
        public int[] avoidFlood(int[] rains) {
            int n = rains.length;
            int[] res = new int[n];
            ArrayList<Integer> zeros = new ArrayList<>();
            HashMap<Integer, Integer> map = new HashMap<>(); // 记录下雨的水池->下雨的日子
            for (int i = 0; i < n; i++) {
                if (rains[i] == 0) {
                    zeros.add(i); // 记录不下雨的日子
                } else {
                    res[i] = -1;
                    int pool = rains[i];
                    if (map.containsKey(pool)) {
                        // Integer zeroIdx = zeros.ceiling(map.get(pool));
                        int lastFull = map.get(pool);
                        int id = lower_bound(zeros, lastFull); // 前一个满了的pool右边的第一个0的index
                        int zeroIdx = id >= zeros.size() ? -1 : zeros.get(id);
                        if (zeroIdx > lastFull) {
                            res[zeroIdx] = pool;
                            zeros.remove(Integer.valueOf(zeroIdx)); // 这里要用Integer装箱；如果不装箱，会outOfBound，因为remove默认的参数代表index
                            map.put(pool, i);// 这里要更新当前满了的Pool的index，不能remove，因为虽然把前一个编号为pool的水池放干了，但是现在又下满了
                        } else {
                            return new int[0];
                        }
                    } else {
                        map.put(pool, i);
                    }
                }
            }
            for (int i : zeros) res[i] = 1; // 根据题意，把所有没有用到的0置为任意正数
            return res;
        }

        /**
         * 二分搜索
         **/
        private int lower_bound(ArrayList<Integer> A, int target) {
            int lo = 0, hi = A.size();
            while (lo < hi) {
                int mid = lo + (hi - lo) / 2;
                if (A.get(mid) >= target) hi = mid;
                else lo = mid + 1;
            }
            return lo;
        }
    }


    class Solution_fail_for_wrong_algorithm {
        public int[] avoidFlood(int[] rains) {
            int[] pre = avoidFlood_prev(rains);
            if (pre.length > 0) return pre;
            return avoidFlood_back(rains);
        }

        public int[] avoidFlood_back(int[] rains) {
            Set<Integer> currentFloodSet = new HashSet<>();
            Set<Integer> nextFloodSet = new HashSet<>();
            int[] ans = new int[rains.length];
            for (int i = rains.length - 1; i >= 0; ) {
                if (rains[i] > 0) {
                    if (currentFloodSet.contains(rains[i])) return new int[0];//不成立情况:遇到重复元素
                    ans[i] = -1;
                    currentFloodSet.add(rains[i]);
                    --i;
                } else {
                    //当前不下雨，则需要向未来找，找哪个id需要排干
                    int curDay = i;
                    while (i >= 0 && rains[i] == 0) --i;
                    int interval = curDay - i;
                    while (i >= 0 && rains[i] != 0) {
                        if (nextFloodSet.contains(rains[i])) return new int[0];//不成立情况:遇到重复元素
                        nextFloodSet.add(rains[i]);
                        ans[i--] = -1;
                    }

                    Set<Integer> commonSet = new HashSet<>(currentFloodSet);
                    commonSet.retainAll(nextFloodSet);
                    if (commonSet.size() > interval || (currentFloodSet.size() == 0 && nextFloodSet.size() > interval))
                        return new int[0];//不成立情况：元素数量大于间隔

                    Iterator<Integer> cit = commonSet.iterator();
                    while (cit.hasNext() && interval-- > 0) {
                        int curLake = cit.next();
                        ans[curDay--] = curLake;
                        nextFloodSet.remove(curLake);
                    }

                    cit = nextFloodSet.iterator();
                    while (cit.hasNext() && interval-- > 0) {
                        int curLake = cit.next();
                        ans[curDay--] = curLake;
                        nextFloodSet.remove(curLake);
                    }

                    while (interval-- > 0) ans[curDay--] = 1;
                    currentFloodSet.addAll(nextFloodSet);
                    nextFloodSet.clear();
                }
            }

            return ans;
        }

        public int[] avoidFlood_prev(int[] rains) {
            Set<Integer> currentFloodSet = new HashSet<>();
            Set<Integer> nextFloodSet = new HashSet<>();
            int[] ans = new int[rains.length];
            for (int i = 0; i < rains.length; ) {
                if (rains[i] > 0) {
                    if (currentFloodSet.contains(rains[i])) return new int[0];//不成立情况:遇到重复元素
                    ans[i] = -1;
                    currentFloodSet.add(rains[i]);
                    ++i;
                } else {
                    //当前不下雨，则需要向未来找，找哪个id需要排干
                    int curDay = i;
                    while (i < rains.length && rains[i] == 0) ++i;
                    int interval = i - curDay;
                    while (i < rains.length && rains[i] != 0) {
                        if (nextFloodSet.contains(rains[i])) return new int[0];//不成立情况:遇到重复元素
                        nextFloodSet.add(rains[i]);
                        ans[i++] = -1;
                    }

                    Set<Integer> commonSet = new HashSet<>(currentFloodSet);
                    commonSet.retainAll(nextFloodSet);
                    if (commonSet.size() > interval || (currentFloodSet.size() == 0 && nextFloodSet.size() > interval))
                        return new int[0];//不成立情况：元素数量大于间隔

                    Iterator<Integer> cit = commonSet.iterator();
                    while (cit.hasNext() && interval-- > 0) {
                        int curLake = cit.next();
                        ans[curDay++] = curLake;
                        currentFloodSet.remove(curLake);
                    }

                    cit = currentFloodSet.iterator();
                    while (cit.hasNext() && interval-- > 0) {
                        int curLake = cit.next();
                        ans[curDay++] = curLake;
                        currentFloodSet.remove(curLake);
                    }

                    while (interval-- > 0) ans[curDay++] = 1;
                    currentFloodSet.addAll(nextFloodSet);
                    nextFloodSet.clear();
                }
            }

            return ans;
        }
    }

    class Solution_pre_travel_fail {
        public int[] avoidFlood(int[] rains) {
            Set<Integer> currentFloodSet = new HashSet<>();
            Set<Integer> nextFloodSet = new HashSet<>();
            int[] ans = new int[rains.length];
            for (int i = 0; i < rains.length; ) {
                if (rains[i] > 0) {
                    if (currentFloodSet.contains(rains[i])) return new int[0];//不成立情况:遇到重复元素
                    ans[i] = -1;
                    currentFloodSet.add(rains[i]);
                    ++i;
                } else {
                    //当前不下雨，则需要向未来找，找哪个id需要排干
                    int curDay = i;
                    while (i < rains.length && rains[i] == 0) ++i;
                    int interval = i - curDay;
                    while (i < rains.length && rains[i] != 0) {
                        if (nextFloodSet.contains(rains[i])) return new int[0];//不成立情况:遇到重复元素
                        nextFloodSet.add(rains[i]);
                        ans[i++] = -1;
                    }

                    Set<Integer> commonSet = new HashSet<>(currentFloodSet);
                    commonSet.retainAll(nextFloodSet);
                    if (commonSet.size() > interval || (currentFloodSet.size() == 0 && nextFloodSet.size() > interval))
                        return new int[0];//不成立情况：元素数量大于间隔

                    Iterator<Integer> cit = commonSet.iterator();
                    while (cit.hasNext() && interval-- > 0) {
                        int curLake = cit.next();
                        ans[curDay++] = curLake;
                        currentFloodSet.remove(curLake);
                    }

                    cit = currentFloodSet.iterator();
                    while (cit.hasNext() && interval-- > 0) {
                        int curLake = cit.next();
                        ans[curDay++] = curLake;
                        currentFloodSet.remove(curLake);
                    }

                    while (interval-- > 0) ans[curDay++] = 1;
                    currentFloodSet.addAll(nextFloodSet);
                    nextFloodSet.clear();
                }
            }

            return ans;
        }
    }

    public void run() {
        Solution solution = new Solution();
        int[] arr = InputUtil.toIntegerArray("[1,3,2,0,2,0,3,0,1,0,0,0]");
        System.out.println(Arrays.toString(solution.avoidFlood(arr)));
    }

    public static void main(String[] args) throws Exception {
        LC1488 an = new LC1488();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
